package AVLtree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//import static BTree.text.isOrder;

/**
 * AVL树
 * 他的左右俩支树的高度差不会超过一（-1 / 0 / 1）
 * 如果有一棵树他的高度是平衡的（不会超过（-1 / 0 / 1）），那么就可以称他为AVL树
 * AVL树的高度可以保持在logN，那么他的搜索的时间复杂度就可以为logN
 */
public class AVLtree {

    static class Node{
        Node right;
        Node left;
        Node parent;
        int bf = 0;//平衡因子
        int val;

        public Node(int val) {
            this.val = val;
        }
    }

    Node root = null;

    //插入
    public Boolean push(int val) {
        Node node = new Node(val);
        if (root == null) {
            root = node;
            return true;//只有一个
        }
        //找到合适的null位置
        Node tmp = root;
        Node parent = root;
        while (tmp != null) {
            if (val < tmp.val) {
                parent = tmp;
                tmp = tmp.left;
            } else if(val > tmp.val){
                parent = tmp;
                tmp = tmp.right;
            }else{//这里要去重
//                System.out.println("val已经存在");
                return false;
            }
        }
        //插入
        if (val > parent.val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        tmp = node;
        tmp.parent = parent;//连接起根left = {AVLtree$Node@736} 节点

        //插入之后要更改平衡因子 是从插入的这个节点向上开始更改 最差会改到root节点
        while (parent != null) {
            if (parent.left == tmp) {//插入的实在跟的左边
                parent.bf--;
            } else { //插入的实在根的右边
                parent.bf++;
            }

            //判断这个节点这个时候是否平衡
            if (parent.bf == 0 ) {//这棵树时平衡的
                break;
            } else if (parent.bf == 1 || parent.bf == -1) {//可能是右边或者左边高一点但是还没有违反AVL树的性质，
                // 那么就继续向上去更改这颗树的bf
                tmp = parent;
                parent = parent.parent;
            } else {//这时的bf==2违反了AVL书的性质那么就要进行旋转
                // 根据tmp的左右不同的高度而会有不桶的插入方式
                if (parent.bf == -2) {//左边过高
                    if (tmp.bf == -1) {//插入较高左树的左侧 用右单旋
                        rotateRight(parent);
                        break;
                    } else{//parentTmp.bf == 1 插入的是在较高左树的右边，左右双旋
                        rotateLeftRight(parent);
                        break;
                    }
                } else {//parent.bf == 2 右边过高 左旋
                    if (tmp.bf == -1) {// 插入的是在较高右树的左边，右左双旋
                        rotateRightLeft(parent);
                        break;
                    } else{//parentTmp.bf == 1 插入的是较高右树的右边，那么使用左单旋
                        rotateLeft(parent);
                        break;
                    }
                }
            }
        }
        return true;
    }

    public boolean contain(int val) {
        Node tmp = root;
        while (tmp != null) {
            if (val > tmp.val) {
                tmp = tmp.right;
            } else if (val < tmp.val) {
                tmp = tmp.left;
            } else {//相等说明存在
                return true;
            }
        }
        return false;
    }

    public boolean del(int val) throws findError{
        //若不存在
        if (!contain(val)) {
            throw new findError("该值不存在 val = " + val);
        }

        //找到该节点
        Node cur = root;
        while (cur != null) {
            if (cur.val > val) {
                cur = cur.left;
            } else if (cur.val < val) {
                cur = cur.right;
            } else { // cur.val == val
                break;
            }
        }


        //替换删除法 用该节点的左支树的最右节点 cur一定存在
        Node tmp = cur.left;
        if (tmp == null) {//不存在左支树
            if (cur == root) {//为根
                root = root.right;
            } else {//不为根
                Node tmpH = cur.parent;
                //不知道parent是那个支树指向cur
                if (tmpH.right == cur) {
                    tmpH.right = cur.right;
                }else{
                    tmpH.left = cur.right;
                }
                if (cur.right != null) {
                    cur.right.parent = tmpH;
                }
            }
            return true;
        }
        //存在左支树的删除
        Node tmpR = tmp.right;
        //找到删除的节点
        while (tmpR != null && tmpR.right != null) {
            tmpR = tmpR.right;
        }
        //替换cur
        if (tmpR != null) {
            cur.val = tmpR.val;
            tmpR.parent.right = null;//删除这个节点的连接
        } else {//tmpR == null
            cur.val = tmp.val;
            cur.left = null;
        }
        return true;
    }
    /**
     * 右左双旋
     * 先对parent.right进行右旋，在对parent进行左旋
     * 再根据插入subRL的左右位置分别对bf进行赋值（parent，subR，subRL）
     * @param parent
     */
    private void rotateRightLeft(Node parent) {
        Node subR = parent.right;
        Node subRL = subR.left;
//        if (subRL == null) {
//            System.out.println("subRL == null");
//        }
//        if (subRL == null) {//有空指针的异常是因为再判断
//        使用这个方法的时候出了错误，应该是根据parent的下一个节点tmp的bf来判断是否使用
        //另一个方法也是这样，当改为tmp.bf之后就正确了
//            return;
//        }
        int bf = subRL.bf;

        rotateRight(subR);
        rotateLeft(parent);

        if (bf == 1) {//subRL == 1
            subR.bf = 0;
            subRL.bf = 0;
            parent.bf = -1;
        } else if(bf == -1){//bf == -1
            subR.bf = 1;
            subRL.bf = 0;
            parent.bf = 0;
        }
    }

    /**
     * 左右双旋
     * 该节点插入在较高左子树的右侧
     * 右侧指的是parent.left的右边
     * 而且又会根据插入对应的根具体的位置进行不同的bf赋值
     * @param parent
     */
    private void rotateLeftRight(Node parent) {
        Node subL = parent.left;
        Node subLR = subL.right;
//        if (subLR == null) {//已经解决
//            System.out.println("subLR == null   \n插入的值为valu = " );
//        }
//        if (subLR == null) {
//            return;
//        }
        int bf = subLR.bf;

        rotateLeft(subL);
        rotateRight(parent);

        //左右双旋后，左单旋或右单旋改变的bf已经不适用了
        //那么需要额外对插入在该节点的左右分俩种情况重新赋值
        if (bf == -1) {//插入的是在该节点的左边
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        } else if(bf == 1){//bf == 1
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

    /**
     * 右单旋
     */
    private void rotateRight(Node parent) {
        Node subL = parent.left;
        Node subLR = subL.right;
        //旋转
        subL.right = parent;

        Node parentH = parent.parent;
        parent.parent = subL;

        parent.left = subLR;
        if (subLR != null) {
            subLR.parent = parent;
        }

        if (parent == root) {
            root = subL;
            subL.parent = null;
        } else {//parent不为根
            if (parentH.left == parent) {
                parentH.left = subL;
                subL.parent = parentH;
            } else {
                parentH.right = subL;
                subL.parent = parentH;
            }
        }
        subL.bf = 0;
        parent.bf = 0;
    }

    /**
     * 左单旋
     */
    private void rotateLeft(Node parent) {
        //记录节点
        Node subR = parent.right;
        Node subRL = subR.left;

        //旋转
        subR.left = parent;

        Node parentH = parent.parent;
        parent.parent = subR;

        parent.right = subRL;
        if (subRL != null) {//可能parent没有左节点
            subRL.parent = parent;
        }

        if (parent == root) {//那么curR就是新的根节点
            root = subR;
            subR.parent = null;
        } else {
            if (parentH.left == parent) {
                parentH.left = subR;//连接起新的根
                subR.parent = parentH;
            } else {
                parentH.right = subR;
                subR.parent = parentH;
            }
        }
        //旋转过后新的根的平衡因子肯定为0
        subR.bf = 0;
        parent.bf = 0;
    }

    //按层来打印树 会将空节点几位null
    public List<List<String>> levelOrder(Node root) {
        List<List<String>> arr = new LinkedList<>();
        if (root == null) {
            return arr;
        } else {
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);

            while(!queue.isEmpty()) {
                int size = queue.size();

                LinkedList tmpL;
                for(tmpL = new LinkedList(); size != 0; --size) {
                    Node tmp = (Node)queue.poll();
                    if (tmp != null) {
                        tmpL.add("" + tmp.val);
                        queue.offer(tmp.left);
                        queue.offer(tmp.right);
                    } else {
                        tmpL.add("null");
                    }
                }

                arr.add(tmpL);
            }

            return arr;
        }
    }
    //获取树的高度
    public int getHeight(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right))+1;
    }

    // 中序遍历是个有序数组
    public boolean isValidBSTBE(Node root) {
        return fun(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean fun(Node root,long min, long max){
        if(root == null) return true;

        if(root.val >= max || root.val <= min){
            return false;
        }

        return fun(root.left, min, root.val) && fun(root.right, root.val, max);
    }
    
    List<Integer> OrderList = new LinkedList<>();
    public boolean isValidBST(Node root) {
        inOrder(root);
        return isOrder(OrderList);
    }

    private boolean isOrder(List<Integer> orderList) {
        for (int i = 0; i < orderList.size()-1; i++) {
            if (orderList.get(i) > orderList.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    private void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        OrderList.add(root.val);
        inOrder(root.right);
    }

}











